package id3;

import java.util.AbstractCollection;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Iterator;

/**
 *
 * @author Rodrigo
 */
public class ArbolDecision {

	////// valores del nodo
	private int atributo; // valor del nodo
	private AbstractList<ParValHijo> hijos; // hijos del nodo
	////// valores estaticos que deben ser rellenados antes de utilizar esta clase
	// aca hay que rellenar con todos los tipos de atributo que puede tener un atributo i
	// por ejemplo, para el atributo 1, los posibles valores son bell=b,conical=c,convex=x,flat=f,knobbed=k,sunken=s
	// recordar que el atributo 0 es el target atribute y puede valer 'e' (comestible) o 'p' (venenoso)
	public static AbstractList<AbstractList<Character>> tipoAtributos;
	public static char targetPositivo = 'e';
	public static char targetNegativo = 'p';

	// ejemplos es una lista con todos los ejemplos de prueba que se van a usar
	// atributos es una lista con todos los atributos que se van a usar, los integer pueden estar entre 1 y 22
	ArbolDecision(AbstractCollection<Ejemplo> ejemplos, AbstractCollection<Integer> atributos) {  // Este es el algoritmo id3

		if (atributos.isEmpty() || todosEjemplosPositivos(ejemplos) || todosEjemplosNegativos(ejemplos)) {
			atributo = 0;
			hijos = new ArrayList<ParValHijo>();
			char hoja = getMasComunTarget(ejemplos);
			hijos.add(new ParValHijo('\0', hoja));
		} else {
			atributo = mejorClasificador(ejemplos, atributos);
			if (atributo == 0) {
				System.out.println("ERROR: ES 0!!!");
			}

			hijos = new ArrayList<ParValHijo>();
			Iterator it = tipoAtributos.get(atributo).iterator();
			while (it.hasNext()) {
				Character ch = (Character) it.next();
				AbstractCollection<Ejemplo> ejemplosvi = getEjemplosvi(ch, ejemplos, atributo);
				if (ejemplosvi.isEmpty()) {
					char hoja = getMasComunTarget(ejemplos);
					hijos.add(new ParValHijo(ch, new ArbolDecision(hoja)));
				} else {
					AbstractCollection<Integer> atributosvi = new ArrayList(atributos);
					atributosvi.remove(atributo);
					hijos.add(new ParValHijo(ch, new ArbolDecision(ejemplosvi, atributosvi)));
				}
			}
		}
	}

	ArbolDecision(char hoja) {
		atributo = 0;
		hijos = new ArrayList<ParValHijo>();
		hijos.add(new ParValHijo('\0', hoja));
	}

	private boolean todosEjemplosPositivos(AbstractCollection<Ejemplo> ejemplos) {
		Iterator it = ejemplos.iterator();
		int cant = 0;
		while (it.hasNext() && ((Ejemplo) it.next()).getVal(0) == targetPositivo) {
			cant++;
		}
		if (ejemplos.size() == cant) {
			return true;
		} else {
			return false;
		}
	}

	private boolean todosEjemplosNegativos(AbstractCollection<Ejemplo> ejemplos) {
		Iterator it = ejemplos.iterator();
		int cant = 0;
		while (it.hasNext() && ((Ejemplo) it.next()).getVal(0) == targetNegativo) {
			cant++;
		}
		if (ejemplos.size() == cant) {
			return true;
		} else {
			return false;
		}
	}

	private char getMasComunTarget(AbstractCollection<Ejemplo> ejemplos) {
		Iterator it = ejemplos.iterator();
		int cantNegativos = 0;
		int cantPositivos = 0;
		while (it.hasNext()) {
			if (((Ejemplo) it.next()).getVal(0) == targetNegativo) {
				cantNegativos++;
			} else {
				cantPositivos++;
			}
		}
		if (cantNegativos > cantPositivos) {
			return targetNegativo;
		} else {
			return targetPositivo;
		}
	}

	private int getCantPositivos(AbstractCollection<Ejemplo> ejemplos) {
		Iterator it = ejemplos.iterator();
		int cantPositivos = 0;
		while (it.hasNext()) {
			if (((Ejemplo) it.next()).getVal(0) == targetPositivo) {
				cantPositivos++;
			}
		}
		return cantPositivos;
	}

	private int getCantNegativos(AbstractCollection<Ejemplo> ejemplos) {
		Iterator it = ejemplos.iterator();
		int cantNegativos = 0;
		while (it.hasNext()) {
			if (((Ejemplo) it.next()).getVal(0) == targetNegativo) {
				cantNegativos++;
			}
		}
		return cantNegativos;
	}

	private AbstractCollection<Ejemplo> getEjemplosvi(char valor, AbstractCollection<Ejemplo> ejemplos, int atributo) {
		AbstractCollection<Ejemplo> ret = new ArrayList();
		Iterator it = ejemplos.iterator();
		while (it.hasNext()) {
			Ejemplo ej = (Ejemplo) it.next();
			if (ej.getVal(atributo) == valor) {
				ret.add(ej);
			}
		}
		return ret;
	}

	public float logOfBase(int base, float num) {
		return (float) (Math.log(num) / Math.log(base));
	}

	private float entropia(AbstractCollection<Ejemplo> ejemplos) {
		if (ejemplos.isEmpty()) {
			return 0;
		}

		int cantPositivos = getCantPositivos(ejemplos);
		if (cantPositivos == 0) {
			return 0;
		}
		int cantNegativos = getCantNegativos(ejemplos);
		if (cantNegativos == 0) {
			return 0;
		}
		return -((float) cantPositivos / (float) ejemplos.size()) * logOfBase(2, (float) cantPositivos / (float) ejemplos.size())
				- ((float) cantNegativos / (float) ejemplos.size()) * logOfBase(2, (float) cantNegativos / (float) ejemplos.size());
	}

	private float ganancia(AbstractCollection<Ejemplo> ejemplos, int atributo) {

		float ret = entropia(ejemplos);
		Iterator it = tipoAtributos.get(atributo).iterator();
		while (it.hasNext()) {
			Character c = (Character) it.next();
			AbstractCollection<Ejemplo> ejs = getEjemplosvi(c, ejemplos, atributo);
			ret -= ((float) ejs.size() / (float) ejemplos.size()) * entropia(ejs);

		}
		return ret;
	}

	private int mejorClasificador(AbstractCollection<Ejemplo> ejemplos, AbstractCollection<Integer> atributos) {
		Iterator it = atributos.iterator();
		int ret = 0;
		float mejorvalor = 0;
		while (it.hasNext()) {
			Integer atrib = (Integer) it.next();
			float gan = ganancia(ejemplos, atrib);
			if (gan > mejorvalor) {
				mejorvalor = gan;
				ret = atrib;
			}
		}
		return ret;
	}

/////////////////////////////////poda///////////////////////////////////////////	
	private boolean evaluar(Ejemplo ejemplo) {
		char valorEjemplo = ejemplo.getVal(atributo);
		Iterator it = this.hijos.iterator();
		if (this.atributo == 0) { // es hoja
			ParValHijo hijo = (ParValHijo) it.next();
			if (!hijo.esHoja()) {
				System.out.println("ERROR: NO ES HOJA!!!!!");
			}
			return hijo.getHoja() == ejemplo.getVal(0);
		} else {
			boolean flag = false;
			ParValHijo hijo = null;
			while (it.hasNext() && !flag) {
				ParValHijo actual = (ParValHijo) it.next();
				if (actual.getValor() == valorEjemplo) {
					hijo = actual;
					flag = true;
				}
			}
			if (hijo == null) {
				System.out.println("ERROR: ES NULL!!!!");
			} else if (hijo.esHoja()) {
				System.out.println("ERROR: ES HOJA!!!!");
			}
			return hijo.getHijo().evaluar(ejemplo);
		}
	}

	int cantidadAciertos(ArrayList ejemplos) {
		int aciertosArbol = 0;
		Iterator it = ejemplos.iterator();
		while (it.hasNext()) {
			if (this.evaluar((Ejemplo) it.next())) {
				aciertosArbol++;
			}
		}
		return aciertosArbol;
	}

	void podar(ArrayList ejemplos) {
		int aciertosMasComun = 0;
		char masComun = getMasComunTarget(ejemplos);
		if (masComun == targetPositivo) {
			aciertosMasComun = getCantPositivos(ejemplos);
		} else {
			aciertosMasComun = getCantNegativos(ejemplos);
		}
		if (this.atributo == 0) { // es una hoja
			char valorDelNodo = ((ParValHijo) this.hijos.iterator().next()).getHoja(); // Puede ser 'e' o 'p'
			if (masComun != valorDelNodo) {
				this.hijos = hijos = new ArrayList<ParValHijo>();
				hijos.add(new ParValHijo('\0', masComun));
			}
		} else { // no es hoja
			if (this.cantidadAciertos(ejemplos) >= aciertosMasComun) { // me sirve
				Iterator it = this.hijos.iterator();
				while (it.hasNext()) {
					ParValHijo actual = (ParValHijo) it.next();
					ArrayList ejmplos_vi = (ArrayList) this.getEjemplosvi(actual.getValor(), ejemplos, atributo);
					actual.getHijo().podar(ejmplos_vi);
				}
			} else { // podo esta rama
				atributo = 0;
				this.hijos = hijos = new ArrayList<ParValHijo>();
				hijos.add(new ParValHijo('\0', getMasComunTarget(ejemplos)));
			}
		}
	}

	static void probar(AbstractCollection<Ejemplo> ejemplos, int poda, int verif,
			AbstractCollection<Integer> atributos) {
		int numInst = ejemplos.size();
		int subNumInst = ejemplos.size() / 10;
		AbstractCollection<Ejemplo> ejemplosCostruir = new ArrayList();
		AbstractCollection<Ejemplo> ejemplosPoda = new ArrayList();
		AbstractCollection<Ejemplo> ejemplosVerif = new ArrayList();
		for (int i = (poda - 1) * subNumInst; i < poda * subNumInst; i++) {
			ejemplosPoda.add((Ejemplo) ((ArrayList) ejemplos).get(i));
		}
		for (int i = (verif - 1) * subNumInst; i < verif * subNumInst; i++) {
			ejemplosVerif.add((Ejemplo) ((ArrayList) ejemplos).get(i));
		}
		int max = 0;
		int min = 0;
		if (poda < verif) {
			min = (poda - 1) * subNumInst;
			max = (verif - 1) * subNumInst;
		} else {
			min = (verif - 1) * subNumInst;
			max = (poda - 1) * subNumInst;
		}
		for (int i = 0; i < min; i++) {
			ejemplosCostruir.add((Ejemplo) ((ArrayList) ejemplos).get(i));
		}
		for (int i = min + subNumInst; i < max; i++) {
			ejemplosCostruir.add((Ejemplo) ((ArrayList) ejemplos).get(i));
		}
		for (int i = max + subNumInst; i < numInst; i++) {
			ejemplosCostruir.add((Ejemplo) ((ArrayList) ejemplos).get(i));
		}
		ArbolDecision ar = new ArbolDecision(ejemplosCostruir, atributos);
		ar.podar((ArrayList) ejemplosPoda);
		int resultado = ar.cantidadAciertos((ArrayList) ejemplosVerif);
		System.out.println("Para poda=" + poda + " y test=" + verif + " el resultado fue: " + resultado + "/" + subNumInst + " evaluadas correctamente");
	}
}
